package hash;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/*
 *@description
 *@author hkfan
 *@version 1.0
 *@create 2025/6/4 16:38
 */
public class LeetCode_1 {
    public int[] twoSum(int[] nums, int target) {
        //0. 记录下标
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])){
                List<Integer> list = map.get(nums[i]);
                list.add(i);
                map.put(nums[i],list);
            }else {
                ArrayList<Integer> list = new ArrayList<>();
                list.add(i);
                map.put(nums[i],list);
            }
        }
        //1. 快排
        Arrays.sort(nums);

        //2. 快慢指针
        int l=0,r=nums.length-1;
        int[] res = new int[2];
        while (l<r){
            if (nums[l]+nums[r]<target){
                l++;
            } else if (nums[l]+nums[r]>target) {
                r--;
            }else {
                if (nums[l]==nums[r]){
                    res[0]=map.get(nums[l]).get(0);
                    res[1]=map.get(nums[l]).get(1);
                }else {
                    res[0]=map.get(nums[l]).get(0);
                    res[1]=map.get(nums[r]).get(0);
                }
                break;
            }
        }
        return res;
    }
}
